<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            单词拆分题目描述：
            给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

            注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

            

            示例 1：

            输入: s = "leetcode", wordDict = ["leet", "code"]
            输出: true
            解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
            示例 2：

            输入: s = "applepenapple", wordDict = ["apple", "pen"]
            输出: true
            解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
                注意，你可以重复使用字典中的单词。
            示例 3：

            输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
            输出: false
            
        */


        /*
            动态规划解法:
            类型：是一个完全背包问题 词典里面的是物品，s字符串是背包

            dp含义：dp[i] 如果dp[i]为true，表示长度为i的字符串能够拆分且出现在字典里面
            递推公式:
                if (
                    [i - wordDict[j].length, i]区间子串出现在字典 &&
                    dp[i - wordDict[j]]是true
                )
                则dp[i]是true
            初始化：
                dp[0]必须为true，字符串为''没有意义，但是方便后面递推
                其他初始为false
            遍历顺序：
                排列问题，因为字符串拼接放到背包必须是有顺序的，如果没有顺序，则是错的 ，applepen可以，但是penapple不行
            举例：
                s="applepenapple"
                wordDict = ["apple", "pen"]
                背包：0 1 2 3 4 5 6 7 8 9 10 11 12 13
                初始化
                dp = [0, false, false, false, false, false, false, false, false, false, false, false, false, false]
                i = 0
                        i > wordDict[j].length
                    j = 0, 
                    j = 1,
                i = 1,
                    j = 0,
                    j = 1,
                i = 2,
                    j = 0,
                    j = 1,
                i = 3,
                    j = 0,
                    j = 1 =>  s.slice(3 - wordDict[j].length, 3) === wordDict[j] 值是false return
                i = 4
                    j = 0
                    j = 1 =>  s.slice(4 - 3, 4) === wordDict[j] 值是false  return 
                i = 5
                    j = 0 => s.slice(5 - 5, 5) === wordDict[j] 值是true && dp[i - wordDict[j].length] 就是dp[5 - 5] = dp[0] = true
                    j = 1 => s.slice(5 - 3, 5) === wordDict[j] 值是aple 不等于pen
                i = 6
                ……
                i = 8
                    j = 0
                    j = 1 => s.slice(8 - 3, 8) 就是 pen和 wordDict[j]相等，是pen && dp[i - wordDict[j].length] = dp[8 - 3] = true
        */


        /* 
            O(n * m)
            O(n)
        */

        const wordBreak = (s, wordDict) => {
            // 初始化 
            let dp = new Array(s.length + 1).fill(false)
            dp[0] = true
            // 遍历顺序，先背包后物品，需要有顺序
            for (let i = 0; i <= s.length; i++) {
                for (let j = 0; j < wordDict.length; j++) {
                   if (i - wordDict[j].length >= 0) {
                        if (s.slice(i - wordDict[j].length, i) === wordDict[j] && dp[i - wordDict[j].length]) {
                            debugger
                            dp[i] = true
                        }
                   } 
                }
            }
            return dp[s.length]
        }
        console.log(wordBreak("applepenapple", ["apple", "pen"]));
        // console.log(wordBreak("leetcode", ["leet", "code"]));
        // console.log(wordBreak("catsandog", ["cats", "dog", "sand",  "and", "o", "cat"]));
    </script>
</body>

</html>